#include "LinkTree.h"
#include <iostream>

TreeNode::TreeNode(const ElementType &element) : data(element)
{
    parent = FirstChild = nextSbling = nullptr;
}

void TreeNode::Connect(TreeNode *parent)
{
    if (!parent)
        return;
    this->parent = parent;
    // 头插
    this->nextSbling = parent->FirstChild;
    parent->FirstChild = this;
}

void TreeNode::DisConnect(TreeNode *parent)
{
    if (parent == nullptr || this->parent != parent)
        return;
    // 把我从双亲的孩子的集合删除
    TreeNode *travelPoint = parent->FirstChild;
    if (this == parent->FirstChild)
    {
        parent->FirstChild = this->nextSbling;
    }
    else
    {
        while (travelPoint->nextSbling != nullptr)
        {
            if (travelPoint->nextSbling == this)
            {
                travelPoint->nextSbling = this->nextSbling;
                break;
            }
            travelPoint = travelPoint->nextSbling;
        }
    }
    parent = nextSbling = nullptr;
}

void TreeNode::FreeNode(TreeNode *node)
{
    if (node == nullptr)
        return;
    FreeNode(node->FirstChild);
    FreeNode(node->nextSbling);
    delete node;
}

void TreeNode::show(TreeNode *node, int depth)
{
    // 终止条件
    if (node == nullptr)
        return;
    for (int i = 0; i < depth; i++)
        std::cout << " ";
    if (depth > 0)
        std::cout << "|_";
    // 排除根结点
    if (node->parent != nullptr)
        std::cout << node->data << std::endl;
    // 深度优先遍历
    show(node->FirstChild, depth + 1);
    show(node->nextSbling, depth);
}

LinkTree::LinkTree()
{
    root = new TreeNode("");
}

LinkTree::LinkTree(const ElementType &element)
{
    root = new TreeNode(element);
}

LinkTree::~LinkTree()
{
    TreeNode::FreeNode(root);
}

TreeNode *LinkTree::GetRoot()
{
    return root;
}

void LinkTree::show()
{
    root->show(root, -1);
}

TreeNode *TreeNode::FindNode(TreeNode *node, const ElementType &element)
{
    // 终止条件
    if (node == nullptr)
        return nullptr;
    // 排除根结点
    if (node->data == element && node->parent != nullptr)
        return node;

    TreeNode *target = FindNode(node->FirstChild, element);
    if (target)
        return target;

    target = FindNode(node->nextSbling, element);
    if (target)
        return target;

    return nullptr;
}

void TreeNode::FindNode(TreeNode *node, const ElementType &element, DArray::DynamicArray &a)
{
    // 终止条件
    if (node == nullptr)
        return;
    // 排除根结点
    if (node->data == element && node->parent != nullptr)
    {
        a.InsertTail(node);
    }
    FindNode(node->FirstChild, element, a);
    FindNode(node->nextSbling, element, a);
}

DArray::DynamicArray LinkTree::FindByElement(const ElementType &element)
{
    DArray::DynamicArray a;
    TreeNode::FindNode(root, element, a);
    return a;
}

// //在树中按值找结点
// TreeNode *LinkTree::FindByElement(const ElementType &element)
// {
//     return TreeNode::FindNode(root,element);
// }

// 找结点高度
int TreeNode::GetNodeHeight(TreeNode *node)
{
    if (node == nullptr)
        return 0;

    int Maxheight = 0;
    // 找最高的那棵子树
    TreeNode *travePoint = node->FirstChild;
    while (travePoint != nullptr)
    {
        int height = GetNodeHeight(travePoint);
        Maxheight = Maxheight > height ? Maxheight : height;
        travePoint = travePoint->nextSbling;
    }
    // 自身高度 = 最高子树高度 + 1
    return Maxheight + 1;
}

// 找树的高度
int LinkTree::GetTreeHeight()
{
    return TreeNode::GetNodeHeight(root) - 1;
}

TreeNode *TreeNode::GetParent()
{
    return parent;
}

std::string &TreeNode::GetData()
{
    return data;
}

void TreeNode::SetData(const ElementType &element)
{
    data = element;
}

std::string LinkTree::GetNodePath(TreeNode *node)
{
    if (node == nullptr)
        return std::string();
    std::string path = node->GetData();
    while (node->GetParent() != nullptr)
    {
        path = node->GetParent()->GetData() + "/" + path;
        node = node->GetParent();
    }
    return path;
}